package Beginner_Algorithm;

public class merge_two_lists {

    public static class list {
        int num;
        list next;

        public list(int i) {
            num = i;
        }
    }

    public static list mergeTwoLists(list head1,list head2) {
        if (head1 == null || head2 == null) {
            return head1==null ? head2 : head1;
        }
        list head = head1.num < head2.num ? head1 : head2;
        list cur1 = head.next;
        list cur2 = head1.num < head2.num ? head2 : head1;
        list pre = head;
        while(cur1 != null && cur2 != null) {
            if (cur1.num < cur2.num) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        pre.next = cur1 == null ? cur2 : cur1;
        return head;
    }

    public static void print(list head) {
        while (head != null) {
            System.out.println(head.num);
            head = head.next;
        }
    }

    public static void main(String[] args) {
        list a1 = new list(2);
        list a2 = new list(5);
        list a3 = new list(8);
        a1.next = a2;
        a2.next = a3;
        list b1 = new list(3);
        list b2 = new list(4);
        list b3 = new list(7);
        b1.next = b2;
        b2.next = b3;
        list test = mergeTwoLists(a1,b1);
        print(test);
    }
}
